package com.linyaonan.leetcode.medium._503;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
 *
 * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,2,1]
 * 输出: [2,-1,2]
 * 解释: 第一个 1 的下一个更大的数是 2；
 * 数字 2 找不到下一个更大的数；
 * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
 * 示例 2:
 *
 * 输入: nums = [1,2,3,4,3]
 * 输出: [2,3,4,-1,4]
 *
 * @author: Lin
 * @date: 2024/10/10
 */
public class NextGreaterElementII {

    /**
     * 还是单调栈的思路，因为有环的存在可以拼接两次数组来避免环的判断情况
     * @param nums
     * @return
     */
    public int[] nextGreaterElements(int[] nums) {

        if (nums.length == 1) {
            return nums;
        }

        int[] de = new int[nums.length * 2];
        System.arraycopy(nums, 0, de, 0, nums.length);
        System.arraycopy(nums, 0, de, nums.length, nums.length);
        // 单调栈
        LinkedList<Integer> list = new LinkedList<>();
        LinkedList<Integer> index = new LinkedList<>();
        list.addLast(nums[0]);
        index.addLast(0);

        int[] result = new int[nums.length];
        Arrays.fill(result, -1);

        for (int i = 0; i < de.length; i++) {
            while (!list.isEmpty() && list.peekLast() < de[i]) {
                result[index.removeLast() % nums.length] = de[i];
                list.removeLast();
            }
            list.addLast(de[i]);
            index.addLast(i);
        }
        return result;
    }

}
